//
// Created by cheng on 2021/03/31.
//

#include <iostream>

using namespace std;
int M[10][10];



int main () {
    int n = 7;
    int p[7] = {4, 2, 3, 1, 2, 2, 3};
    // 记录矩阵Mi-Mj之间的最少乘法次数
    // 初始化Mi-Mi为0
    for (int i = 1; i <= n; i++) {
        M[i][i] = 0;
    }

    // 参与运算的矩阵的个数从2增加到n
    for (int len = 2; len <= n; len++) {
        // 参与运算第一个矩阵从M1到Mn
        for (int i = 1; i <= n-len+1; i++) {
            // 设置最后一个参与运算的矩阵
            int j = i+len-1;
            M[i][j] = (len << 21);
            // 遍历，运算Mi-Mk，k从i到j-1
            for (int k = i; k <= j-1; k++) {
                int a = M[i][j], b = M[i][k], c = M[k+1][j];
                int d = p[i-1], e = p[k], f = p[j];
                int g = d*e*f;
                M[i][j] = min(a, b+c+g);
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            cout << M[i][j] << " ";
        }
        cout << endl;
    }
    cout << M[1][n-1] << endl;
}